package ink.lovejinhu.swardToOffer;

/**
 * @Author: jin
 * @ClassName: Person
 * @Date: 2021/8/20 0:16
 * @Version: V1.0
 **/
public class Offer_012 {
    /**
     * 矩阵中的路径
     * 回溯，bfs
     *
     * @param board
     * @param word
     * @return
     */
    public boolean exist(char[][] board, String word) {
        int[][] ints = new int[board.length][board[0].length];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (dfs(board, word, 0, i, j, ints)) {
                    return true;
                }
            }
        }
        return false;
    }

    public boolean dfs(char[][] board, String word, int index, int row, int column, int[][] ints) {
        if (row < 0 || row >= board.length || column < 0 || column >= board[row].length) {  //证明已经越界了
            return false;
        }
        if (ints[row][column] == 1) {   //拜访过
            return false;
        }
        if (index > word.length() - 1) {   //true的时候忽略了一种情况
            return true;
        } else if (board[row][column] == word.charAt(index) && index == word.length() - 1) {
            return true;
        }

        if (board[row][column] != word.charAt(index)) {  //不相等
            return false;
        }
        //相等的话
        ints[row][column] = 1;   //这个点已经拜访过了
        boolean flag = dfs(board, word, index + 1, row + 1, column, ints) ||
                dfs(board, word, index + 1, row - 1, column, ints) ||
                dfs(board, word, index + 1, row, column + 1, ints) ||
                dfs(board, word, index + 1, row, column - 1, ints);
        ints[row][column] = 0;//还原
        return flag;

    }


}
